1. Field
This disclosure relates generally to program flow control analysis in a data processing system and more specifically to deductive reaching definition analysis.
2. Description of the Related Art
A control flow graph (CFG) of a computer program represents all paths that might be traversed during execution of the computer program. The graph depicts the logic flow in terms of branching, transfer of control, among related nodes of the computer program. Many compiler optimizations and static analysis tools typically use a control flow graph.
Each node in the control flow graph represents a basic block. A basic block is a portion of code without any jumps or branches. A target of a branch starts a new block, and a branch ends a block. Directed edges represent branches within the control flow. An entry block is used to represent where control enters into the flow graph, and an exit block is used to represent where control flow leaves the block. Blocks to which control may transfer after reaching the end of a specific block are called successors of the specific, while the blocks from which control may have come to a specific block are called predecessors of the specific block.
Reaching definitions is a control flow graph property useful in optimization. A reaching definition for a given instruction is another instruction, in which the target variable may reach the given instruction without an intervening assignment. That is the variable may not receive an intervening change in value. For example, a variable a set to a=1 in a first instruction of a first block and set to a value of 2 in a fifth instruction of the same block. The setting of the variable to a value of 2 is an intervening change that ends the possibility of the variable with a value of 1 reaching a subsequent block.
A traditional reaching definition analysis uses a graph-theoretic notion of reaching by declaring that a definition reaches a use if there is some path in the control flow graph from the definition leading to the use that contains no intervening definition of the same variable. This definition of reaching is a conservative approximation.
Typical data flow analysis uses a conservative approximation for possible values a variable may have. The conservative approach does not allow speculation of what value a variable may possess. Therefore, when a value of a variable is unknown at a point in a program execution, and following a conservative approach, the value cannot be excluded. Hence a setting of one variable may be presumed to imply nothing with regard to the setting of another value. For example, when a initial set of variables a=a1, b=b1, c=c1 and d=d1 flows through a set of blocks where in one block c=c2 and d=d2, in another block b=b2 and d=d3, and further through a control point c==c2, nothing can be said with regard to the disposition of values of d other than d cannot equal d1 because d was set to d2 and d3. Therefore, as a result of ordinary analysis both instances of b1, b2 and d2, d3 need to be included as reaching definitions when such inclusion may not be meaningful. The result lacks precision.